package main

import "fmt"

func fibonacci(n int) int {
	if n == 0 || n == 1 {
		return n
	}
	return fibonacci(n-1) + fibonacci(n-2)
}

func fibonacci_dynamic(n int) int {
	cur, nxt := 0, 1
	for i := 0; i < n; i++ {
		cur, nxt = nxt, cur+nxt
	}
	return cur
}

func fibonacci_tail_call(n int) int {
	var call func(n int, cur int, nxt int) int
	call = func(n int, cur int, nxt int) int {
		if n == 0 {
			return cur
		}
		return call(n-1, nxt, cur+nxt)
	}
	return call(n, 0, 1)
}

func main() {
	fmt.Println(fibonacci(30))
	fmt.Println(fibonacci_dynamic(30))
	fmt.Println(fibonacci_tail_call(30))
}
